package mg.system.util;

public class MGHashMap {

	/** The default capacity is 16, this results in an internal size of 21 */
	public static final int DEFAULT_INITIAL_CAPACITY = 16;
	/**
	 * The default load factor is 75 (=75%), so the HashMap is increased when
	 * 75% of it's capacity is reached
	 */
	public static final int DEFAULT_LOAD_FACTOR = 75;

	private final int loadFactor;
	Element[] buckets;
	private final boolean isPowerOfTwo;
	int size;

	/**
	 * Creates a new HashMap with the default initial capacity 16 and a load
	 * factor of 75%.
	 */
	public MGHashMap() {
		this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

	/**
	 * Creates a new HashMap with the specified initial capacity.
	 * 
	 * @param initialCapacity
	 *            the initial number of elements that this map can hold without
	 *            needing to increase it's internal size. Must not be 0.
	 */
	public MGHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR);
	}

	/**
	 * Creates a new HashMap with the specified initial capacity and the
	 * specified load factor.
	 * 
	 * @param initialCapacity
	 *            the initial number of elements that this map can hold without
	 *            needing to increase it's internal size.
	 * @param loadFactor
	 *            the loadfactor in percent, a number between 0 and 100. When
	 *            the loadfactor is 100, the size of this map is only increased
	 *            after all slots have been filled.
	 * @throws IllegalArgumentException
	 *             when the initialCapacity is less than 1
	 */
	public MGHashMap(int initialCapacity, int loadFactor) {
		if (initialCapacity <= 0) {
			throw new IllegalArgumentException();
		}
		// check if initial capacity is a power of 2:
		initialCapacity = (initialCapacity * 100) / loadFactor;
		int capacity = 1;
		while (initialCapacity > capacity) {
			capacity <<= 1;
		}
		this.isPowerOfTwo = (capacity == initialCapacity);
		// System.out.println("isPowerOfTwo: " + this.isPowerOfTwo );
		this.buckets = new Element[initialCapacity];
		this.loadFactor = loadFactor;
	}

	public Object put(Object key, Object value) {

		if (key == null || value == null) {
			throw new IllegalArgumentException(
					"HashMap cannot accept null key [" + key + "] or value ["
							+ value + "].");
		}
		if ((this.size * 100) / this.buckets.length > this.loadFactor) {
			increaseSize();
		}

		int hashCode = key.hashCode();
		int index;
		if (this.isPowerOfTwo) {
			index = (hashCode & 0x7FFFFFFF) & (this.buckets.length - 1);
		} else {
			index = (hashCode & 0x7FFFFFFF) % this.buckets.length;
		}
		Element element = this.buckets[index];
		if (element == null) {
			element = new Element(hashCode, key, value);
			this.buckets[index] = element;
			this.size++;
			return null;
		}
		// okay, there is a collision:
		Element lastElement = element;
		do {
			if (element.key.equals(key)) {
				Object oldValue = element.value;
				element.value = value;
				return oldValue;
			}
			lastElement = element;
			element = element.next;
		} while (element != null);
		// now insert new element at the end of the bucket:
		element = new Element(hashCode, key, value);
		lastElement.next = element;
		this.size++;
		return null;
	}

	public Object get(Object key) {
		if (key == null) {
			throw new IllegalArgumentException();
		}
		int index;
		if (this.isPowerOfTwo) {
			index = (key.hashCode() & 0x7FFFFFFF) & (this.buckets.length - 1);
		} else {
			index = (key.hashCode() & 0x7FFFFFFF) % this.buckets.length;
		}
		Element element = this.buckets[index];
		if (element == null) {
			return null;
		}
		do {
			if (element.key.equals(key)) {
				return element.value;
			}
			element = element.next;
		} while (element != null);
		return null;
	}

	public Object remove(Object key) {

		if (key == null) {
			throw new IllegalArgumentException();
		}
		int index;
		if (this.isPowerOfTwo) {
			index = (key.hashCode() & 0x7FFFFFFF) & (this.buckets.length - 1);
		} else {
			index = (key.hashCode() & 0x7FFFFFFF) % this.buckets.length;
		}
		Element element = this.buckets[index];
		if (element == null) {
			// System.out.println("remove: No bucket found for key " + key +
			// ", containsKey()=" + containsKey(key));
			return null;
		}
		Element lastElement = null;
		do {
			if (element.key.equals(key)) {
				if (lastElement == null) {
					this.buckets[index] = element.next;
				} else {
					lastElement.next = element.next;
				}
				this.size--;
				return element.value;
			}
			lastElement = element;
			element = element.next;
		} while (element != null);
		// System.out.println("No element found for key " + key +
		// ", containsKey()=" + containsKey(key));
		return null;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.enough.polish.util.Map#isEmpty()
	 */
	public boolean isEmpty() {
		return (this.size == 0);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.enough.polish.util.Map#size()
	 */
	public int size() {
		return this.size;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.enough.polish.util.Map#containsKey(java.lang.Object)
	 */
	public boolean containsKey(Object key) {
		return get(key) != null;
	}

	public boolean containsValue(Object value) {
		for (int i = 0; i < this.buckets.length; i++) {
			Element element = this.buckets[i];
			while (element != null) {
				if (element.value.equals(value)) {
					return true;
				}
				element = element.next;
			}
		}
		return false;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.enough.polish.util.Map#clear()
	 */
	public void clear() {
		for (int i = 0; i < this.buckets.length; i++) {
			this.buckets[i] = null;
		}
		this.size = 0;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.enough.polish.util.Map#values()
	 */
	public Object[] values() {
		return values(new Object[this.size]);

	}

	public Object[] values(Object[] objects) {
		int index = 0;
		for (int i = 0; i < this.buckets.length; i++) {
			Element element = this.buckets[i];
			while (element != null) {
				objects[index] = element.value;
				index++;
				element = element.next;
			}
		}
		return objects;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.enough.polish.util.Map#keys()
	 */
	public Object[] keys() {
		return keys(new Object[this.size]);

	}

	public Object[] keys(Object[] objects) {
		int index = 0;
		for (int i = 0; i < this.buckets.length; i++) {
			Element element = this.buckets[i];
			while (element != null) {
				objects[index] = element.key;
				index++;
				element = element.next;
			}
		}
		return objects;
	}

	/**
	 * Returns String containing the String representations of all objects of
	 * this map.
	 * 
	 * @return the stored elements in a String representation.
	 */
	public String toString() {
		StringBuffer buffer = new StringBuffer(this.size * 23);
		buffer.append(super.toString()).append("{\n");
		Object[] values = values();
		for (int i = 0; i < values.length; i++) {
			buffer.append(values[i]);
			buffer.append('\n');
		}
		buffer.append('}');
		return buffer.toString();
	}

	/**
	 * Increaases the internal capacity of this map.
	 */
	private void increaseSize() {
		int newCapacity;
		if (this.isPowerOfTwo) {
			newCapacity = this.buckets.length << 1; // * 2
		} else {
			newCapacity = (this.buckets.length << 1) - 1; // * 2 - 1
		}
		Element[] newBuckets = new Element[newCapacity];
		for (int i = 0; i < this.buckets.length; i++) {
			Element element = this.buckets[i];
			while (element != null) {
				int index;
				if (this.isPowerOfTwo) {
					index = (element.hashCodeValue & 0x7FFFFFFF)
							& (newCapacity - 1);
				} else {
					index = (element.hashCodeValue & 0x7FFFFFFF) % newCapacity;
				}
				Element newElement = newBuckets[index];
				if (newElement == null) {
					newBuckets[index] = element;
				} else {
					// add element at the end of the bucket:
					while (newElement.next != null) {
						newElement = newElement.next;
					}
					newElement.next = element;

				}
				Element lastElement = element;
				element = element.next;
				lastElement.next = null;
			}
		}
		this.buckets = newBuckets;
	}

	private static final class Element {
		public final Object key;

		public final int hashCodeValue;

		public Object value;

		public Element next;

		public Element(int hashCode, Object key, Object value) {

			this.hashCodeValue = hashCode;
			this.key = key;
			this.value = value;
		}
	}

}
